package offer;

/**
 * @author ZhanBo
 * @date 2020/5/25
 */
public class Solution15 {


    public static void main(String[] args) {
        System.out.println(hammingWeight(9));
    }

    /**
     *请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
     *
     * 输入：00000000000000000000000000001011
     * 输出：3
     * 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'.
     *
     * 输入：00000000000000000000000010000000
     * 输出：1
     * 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
     *
     *
     * @param n
     * @return
     */
    public static int hammingWeight(int n) {
        if (n==0 || n ==1) {
            return n;
        }
        int result = 0;
        //将n转为二进制字符串
        String s = Integer.toBinaryString(n);
        char[] array = s.toCharArray();
        for (char c : array){
            if (c == '1'){
                result++;
            }
        }
        return result;
    }

    /**
     * 方法一：逐位判断
     * 根据 与运算 定义，设二进制数字 nn ，则有：
     *      若 n \& 1 = 0n&1=0 ，则 nn 二进制 最右一位 为 00 ；
     *      若 n \& 1 = 1n&1=1 ，则 nn 二进制 最右一位 为 11 。
     * 根据以上特点，考虑以下 循环判断 ：
     *      判断 nn 最右一位是否为 11 ，根据结果计数。
     *      将 nn 右移一位（本题要求把数字 nn 看作无符号数，因此使用 无符号右移 操作）
     *算法流程：
     * 初始化数量统计变量 res = 0res=0 。
     * 循环逐位判断： 当 n = 0n=0 时跳出。
     *      res += n & 1 ： 若 n \& 1 = 1n&1=1 ，则统计数 resres 加一。
     *      n >>= 1 ： 将二进制数字 nn 无符号右移一位（ Java 中无符号右移为 ">>>" ） 。
     * 返回统计数量 resres 。
     *
     *
     * @param n
     * @return
     */
    public static int hammingWeight1(int n) {
        int res = 0;
        while(n != 0) {
            res += n & 1;
            n >>>= 1;
        }
        return res;
    }
}
